package com.lry.basic.algorithm.common;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/10/10
 */

import java.awt.*;
import java.util.LinkedList;
import java.util.Stack;

/**
 * 给定一个二维网格和一个单词，找出该单词是否存在于网格中。
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 * 示例:
 * board =
 * [
 *   ['A','B','C','E'],
 *   ['S','F','C','S'],
 *   ['A','D','E','E']
 * ]
 *
 * 给定 word = "ABCCED", 返回 true.
 * 给定 word = "SEE", 返回 true.
 * 给定 word = "ABCB", 返回 false.
 *
 */
public class WordSearch {
    public static void main(String[] args) {
        System.out.println(
                new WordSearch().exist(
                new char[][]{{'A','C','C','F'},{'S','F','C','S'},{'A','D','E','E'}},
                "FCSEEDAS"));
    }



    public boolean exist(char[][] board, String word) {
        m = board.length;
        if(m==0||word.length()==0)return false;
        n = board[0].length;
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
                if(board[i][j]==word.charAt(0)){
                    if(exist(board,word,i,j)){
                        return true;
                    }
                }
            }
        }
        return false;
    }



    private int m,n;
    private int[][] direction = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};

    public boolean exist(char[][] board, String word,int i,int j) {
        int len = 1;
        int[][] mark = new int[board.length][board[0].length];
        Stack<int[]> stack = new Stack<>();
        stack.push(new int[]{i,j,len});

        //  i-1,j(上)  i,j-1(左)  i,j+1(右)  i+1,j(下)
        while(!stack.isEmpty()){
            //只peek不pop
            int x = stack.peek()[0];
            int y = stack.peek()[1];
            len = stack.peek()[2];
            //出口
            if(len==word.length())return true;
            //坑已被占了，此路不通
            if(mark[x][y]==1){
                stack.pop();
                mark[x][y]=0;
                continue;
            }
            //占坑
            mark[x][y]=1;
            //遍历四个方向
            for(int k=0;k<4;k++){
                //新坐标
                int newX = x+direction[k][0];
                int newY = y+direction[k][1];
                //符合条件就入栈
                if(inRange(newX,newY)&&word.charAt(len)==board[newX][newY]&&mark[newX][newY]!=1){
                    stack.push(new int[]{newX,newY,len+1});
                }
            }
        }
        return false;
    }
    private boolean inRange(int i,int j){
        if(i>=0&&i<m&&j>=0&&j<n){
            return true;
        }
        return false;
    }
}
